Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Ho costruito in vb.net un selecter, che si occupa per la selezione, deselezione e la verifica di cordinate selezionate
Ho implementato selecter combinando una griglia(X,Y) e List(point)
Devo creare una funzione che mi restituisce un array(vettori) di punti appartenenti a un rettangolo passato come argomento.
Es ho una griglia di 4x4 di punti selezionati o no
1001
0101
0010
1011
lista di punti selezionati:
[0,0]
[3,0]
[1,1]
[3,1]
[2,2]
[0,3]
[2,3]
[3,3]
(i punti 1 sono quelli selezionati e quelli 0 no)
Il problema è come selezionare i punti all' interno es del rettangolo [1,1] con dimensioni 2,2. Mi deve restituire [1,1] e [2,2].
Devo scegliere il miglior algoritmo (più veloce). 2 possibili algoritmi sono
Codice sorgente - presumibilmente Plain Text
FUNZIONE getPuntiSelezionatiInRettangolo(sel, rett) punto[]
//Dichiara la lista dei punti
punti[]
//controlla ogni punto appartenente al rettangolo
per x = rett.x a rett.x + rett.width - 1
per y = rett.y a rett.y + rett.height - 1
//verifica se è selezionato
se (sel.isSelected(x,y)) allora punti.aggiungi(new punto(x,y))
fine per
fine per
restituisce punti
FINE FUNZIONE
Questo algoritmo funziona ciclando x e y e verificando ogni punto se è selezionato
Invece questo cicla la lista
Codice sorgente - presumibilmente Algoritmi
FUNZIONE getPuntiSelezionatiInRettangolo(sel, rett) punto[]
//Dichiara la lista dei punti
punti[]
//controlla ogni punto selezionato
per ogni p in sel.getPuntiSelezionati()
//verifica se appartiene al rettangolo
se rett.intersecaPunto(p) allora punti.aggiungi(p)
fine per
restituisci punti
FINE FUNZIONE
entrambi hanno i pro e contro:
PRO per il primo: il massimo tempo è rett.width*rett.height,però se non c'è nessun punto selezionato, la funzione in pratica fa pardere tempo
PRO per il secondo: se la lista è abbastanza corta(< rett.width*rett.height) può essere conveniente, ma se è lunghissima(per esempio 1000 item) può impiegarci un sacco di tempo per la ricerca.
L'idea che mi è appena venuto in mente è quello di verificare la dimensione della lista e l'area del rettangolo, scegliendo il primo algoritmo se l'area è minore, altrimenti l'altro
I punti sono dati tramite un input del tipo "mappa"
Codice sorgente - presumibilmente Plain Text
1001
0101
0010
1011
oppure del tipo "elenco di coordinate"?
Codice sorgente - presumibilmente Plain Text
[0,0]
[3,0]
[1,1]
[3,1]
[2,2]
[0,3]
[2,3]
[3,3]
Lo chiedo perché l'algoritmo 1 (quella che cicla su x e y) va bene se l'input è del tipo "mappa". Infatti conoscendo le coordinate del rettangolo vai subito a vedere i punti che ti interessano e ignori i restanti.
Invece se l'input è come "l' elenco di coordinate" conviene il secondo algoritmo in quanto in ogni caso dovrai leggere per forza tutto il file (altrimenti rischi di perderti qualche punto) e di verificare per ogni riga se il punto è compreso o meno nel rettangolo.
Spero di essere stato chiaro
Ho cercato soluzioni alternative ma non me ne sono venute in mente. Sono curioso di vedere le idee degli altri
entrambi. nella reale implementazione la mappa è di tipo linkedListNode(of point)()() che puntano alla lista linkedList(of point). Ho usate entrambe le strutture per migliore le operazioni.
Per es, per selezionare un punto, se uso la mappa è O(1), invece la lista O(n), altri es se uso getPuntiSelezionati() (nome nel codice GetSelections()), se uso la mappa è O(n), invece la lista O(1).
![Algoritmi - [Algoritmo] Algoritmo per il filtraggio di cordinate](/data/logos/logositov9.png)
